package net.tp.parallel;

import java.util.concurrent.*;
import net.tp.algo.sort.*;

public class ParallelQuickSort {
    public static ForkJoinPool pool = new ForkJoinPool();

    public static class SortAction extends RecursiveAction {

        public static final long serialVersionUID = 1;

        private final int[] a;
        private final int lo;
        private final int hi;
        public SortAction(int[] a, int lo, int hi) {
            this.a = a; this.lo = lo; this.hi = hi;
        }

        @Override
        protected void compute() {
            if (lo < hi) {
                int pv = a[pivot(a, lo, hi)];
                int lt = lo, gt = hi, i = lo;
                while (i <= gt) {
                    if (a[i] < pv) swap(a, lt++, i++);
                    else if (a[i] == pv) i++;
                    else swap(a, i, gt--);
                }

                SortAction worker1 = new SortAction(a, lo, lt-1);
                SortAction worker2 = new SortAction(a, gt+1, hi);

                if (lt - lo > hi - gt) {
                    // fork the smaller task
                    SortAction tmp = worker1;
                    worker1 = worker2;
                    worker2 = tmp;
                }

                worker1.fork();
                worker2.compute();
                worker1.join();
            }
        }
    }


    public static void sort(int[] a) {
        pool.invoke(new SortAction(a, 0, a.length -1 ));
    }

    private static void swap(int[] a, int i, int j) {
        if (i != j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }


    /**
     * <p>Select pivot.</p>
     *
     * <p>There are many strategies to select the pivot. This implementation uses "the Ninther" strategy.</p>
     *
     * @param a
     * @param lo
     * @param hi
     * @return the index of the pivot
     */
    private static int pivot(int[] a, int lo, int hi) {

        int mid = (lo + hi) >>> 1;

        if (hi - lo < 9) {
            return medianOf3(a, lo, mid, hi);
        }
        else {
            int d = (lo + mid) >>> 2;
            return medianOf3(a,
                    medianOf3(a, lo, lo+d, lo+2*d),
                    medianOf3(a, mid-d, mid, mid+d),
                    medianOf3(a, hi-2*d, hi-d, hi)
                    );
        }
    }

    private static int medianOf3(int[] a, int lo, int mid, int hi) {
        if (a[lo] <= hi) {
            if (a[mid] <= a[lo]) return lo;
            else return a[mid] <= a[hi] ? mid : hi;
        }
        else {
            if (a[mid] <= a[hi]) return hi;
            else return a[mid] <= a[lo] ? mid : lo;
        }
    }


}
